package day_2022_7_to_8.day48;

/**
 * @author haomin
 * @date 2022/08/30 15:07
 **/
public class Day45_8_Offer14_Ⅱ_CuttingRope {
    class Solution {
        public int cuttingRope(int n) {
            if(n < 4) return n-1;
            long sum = 1;
            while(n > 4){
                sum = (sum * 3) % 1000000007;
                n -= 3;
            }
            return (int)(sum * n % 1000000007);
        }
    }
}